//
// Created by 86152 on 2021/5/4.
//

#include "part5.h"
#include <iostream>
#include <queue>
#include <stack>

namespace part5_binaryTree{

    tree::tree(int num) : size(num) {
        this->root = new int[num];

        for (int i = 0; i < num; ++i) {
            this->root[i] = i + 1;
        }
    }

    tree::~tree() {
        delete [] this->root;
    }


    // 迭代前序遍历
    void tree::iter_pre_order(){
        int head = 0;
        std::stack<int> stack;
        while (head < this->size || !stack.empty()){
            if (head < this->size){
                this->visit(this->root[head]);  // 前序访问
                stack.push(head);
                head = head * 2 + 1;
            }else {
                head = stack.top();
                stack.pop();
                head = head * 2 + 2;
            }
        }
    }
    void tree::iter_in_order(){
        int head = 0;
        std::stack<int> stack;
        while (head < this->size || !stack.empty()){
            if (head < this->size){
                stack.push(head);
                head = head * 2 + 1;
            }else {
                head = stack.top();
                stack.pop();
                this->visit(this->root[head]);  // 中序遍历
                head = head * 2 + 2;
            }
        }
    }
    void tree::iter_post_order(){
        int head = 0;
        std::stack<int> stack;
        int last = -1;

        while (head < this->size || !stack.empty()){
            if (head < this->size){
                stack.push(head);
                head = head * 2 + 1;
            }else{
                int top_right = stack.top() * 2 + 2;  // 获取顶部元素右孩子
                if (top_right >= this->size || top_right == last){  // 如果右孩子不存在或者右孩子访问过
                    last = stack.top(); // 访问顶部元素
                    this->visit(this->root[last]);
                    stack.pop(); // 弹出顶部元素
                }else{
                    head = top_right;  // head指向右孩子
                }
            }
        }
    }


    void tree::iter_level_order(){
        std::queue<int> queue;
        queue.push(0);

        while (!queue.empty()){
            int queue_size = queue.size();
            for (int i = 0; i < queue_size; ++i) {
                int head = queue.front();
                queue.pop();
                this->visit(this->root[head]);
                if (head * 2 + 1 < this->size){
                    queue.push(head * 2 + 1);
                }
                if (head * 2 + 2 < this->size){
                    queue.push(head * 2 + 2);
                }
            }

        }

    }

    void tree::recu_pre_order(int node){
        if (node >= this->size)return;
        this->visit(root[node]);
        recu_pre_order(node * 2 + 1);
        recu_pre_order(node * 2 + 2);
    }

    void tree::recu_in_order(int node){
        if (node >= this->size)return;
        recu_in_order(node * 2 + 1);
        this->visit(root[node]);
        recu_in_order(node * 2 + 2);
    }

    void tree::recu_post_order(int node){
        if (node >= this->size)return;
        recu_post_order(node * 2 + 1);
        recu_post_order(node * 2 + 2);
        this->visit(root[node]);
    }

    void tree::visit(int i) {
        std::cout << i << "  ";
    }
    void tree::pre_visit(const char* msg) {
        std::cout << msg << std::endl;
    }

    void tree::post_visit(const char* msg) {
        std::cout << msg << "  ";
    }


    void test(){
        part5_binaryTree::tree tree =  part5_binaryTree::tree(7);


        std::cout << "recure   pre  ";
        tree.recu_pre_order(0);
        std::cout << std::endl;

        std::cout << "recure order  ";
        tree.recu_in_order(0);
        std::cout << std::endl;

        std::cout << "recure post   ";
        tree.recu_post_order(0);
        std::cout << std::endl;

        std::cout << "iter  level   ";
        tree.iter_level_order();
        std::cout << std::endl;

        std::cout << "iter   order  ";
        tree.iter_pre_order();
        std::cout << std::endl;

        std::cout << "iter inorder  ";
        tree.iter_in_order();
        std::cout << std::endl;

        std::cout << "iter    post  ";
        tree.iter_post_order();
        std::cout << std::endl;
    }
}



// 按照需要的顺序遍历，每次线索化前一个节点的right和当前节点的left
// 需要一个全过程可见的变量跟踪前一个节点, 而递归又是值传递
// 解决办法： 1、使用二级指针 2、使用一级指针的引用  3、使用全局变量
// 线索化规则：如果left==null，left指向前一个，right==null，right指向后一个
namespace part5_threadTree{
    void pre_thread(Utils::ThreadTreeNode* root ,Utils::ThreadTreeNode** pre){
        if (root == nullptr) return;

        // 线索化当前节点的左节点
        if (root->left == nullptr){
            root->left = *pre;
            root->ltag = 1;
        }

        // 线索化前一个节点的右节点
        if (*pre != nullptr && (*pre)->right == nullptr){
            (*pre)->right = root;
            (*pre)->rtag = 1;
        }

        // 修改全局可见的变量
        *pre = root;

        // 向左右线索化递归
        if (root->ltag == 0){
            pre_thread((Utils::ThreadTreeNode*)root->left, pre);
        }
        if (root->rtag == 0){
            pre_thread((Utils::ThreadTreeNode*)root->right, pre);
        }
    }


    // 二叉树中序线索化，二级指针
    void order_thread(Utils::ThreadTreeNode* root ,Utils::ThreadTreeNode** pre){
        if (root == nullptr) return;

        // 递归
        if (root->ltag == 0){
            order_thread((Utils::ThreadTreeNode*)root->left, pre);
        }

        // 对当前节点的左节点线索化
        if (root->left == nullptr){
            root->left = *pre;
            root->ltag = 1;
        }

        // 对前一个节点的右节点线索化
        if (*pre != nullptr && (*pre)->right == nullptr){
            (*pre)->right = root;
            (*pre)->rtag = 1;
        }

        // 设置pre
        *pre = root;

        // 递归
        if (root->rtag == 0){
            order_thread((Utils::ThreadTreeNode*)root->right, pre);
        }
    }

    // 二叉树后序线索化，二级指针
    void post_thread(Utils::ThreadTreeNode* root ,Utils::ThreadTreeNode** pre){
        if (root == nullptr) return;

        // 递归
        if (root->ltag == 0){
            post_thread((Utils::ThreadTreeNode*)root->left, pre);
        }

        // 递归
        if (root->rtag == 0){
            post_thread((Utils::ThreadTreeNode*)root->right, pre);
        }

        // 对当前节点的左节点线索化
        if (root->left == nullptr){
            root->left = *pre;
            root->ltag = 1;
        }

        // 对前一个节点的右节点线索化
        if (*pre != nullptr && (*pre)->right == nullptr){
            (*pre)->right = root;
            (*pre)->rtag = 1;
        }

        // 设置pre
        *pre = root;
    }


    void test() {

        for (int j = 0; j < 3; ++j) {
            int list[] = {1,2,3,4,5,6,7};
            Utils::TreeManager manager;
            Utils::TreeNode* root = manager.getThreadTreeRoot(list, 7);
            Utils::ThreadTreeNode* pre = nullptr;

            if (j == 0){
                std::cout << "pre thread tree" << std::endl << std::endl;
                pre_thread((Utils::ThreadTreeNode*)root, &pre);
            }
            if (j == 1){
                std::cout << "order thread tree" << std::endl << std::endl;
                order_thread((Utils::ThreadTreeNode*)root, &pre);
            }
            if (j == 2){
                std::cout << "post thread tree" << std::endl << std::endl;
                post_thread((Utils::ThreadTreeNode*)root, &pre);
            }

            for (auto i : manager.pool) {
                Utils::ThreadTreeNode* v = (Utils::ThreadTreeNode*) i;
                std::cout << v << " " << v->left << " " << v->ltag << " " <<  v->value << " " << v->rtag << " " << v->right << std::endl;
            }
            manager.destory();
            std::cout << "=============" << std::endl;
        }
    }
}